package com.wz.leetcode.backtrack;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Subset_78 {

    public static List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        if (len == 0) {
            return result;
        }
        Deque<Integer> tmp = new ArrayDeque<>();
        dfs(0, nums, tmp, result);
        return result;
    }

    private static void dfs(int index,
                            int[] nums,
                            Deque<Integer> tmp,
                            List<List<Integer>> result) {
        if (index == nums.length) {
            result.add(new ArrayList<>(tmp));
            return;
        }
        // 不选择则nums[i]
        dfs(index + 1, nums, tmp, result);

        // 选择则nums[i]
        tmp.addLast(nums[index]);
        dfs(index + 1, nums, tmp, result);
        tmp.removeLast();
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1,2,3}));
        System.out.println(subsets(new int[]{0}));
    }
}
